<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 5.1</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 5.1" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 5.1" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />
<link href="5_002e2.xhtml#g_t5_002e2" rel="next" title="5.2" />
<link href="Chapter-5.xhtml#Chapter-5" rel="prev" title="Chapter 5" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t5_002e1"></a>
<nav class="header">
<p>
Next: <a href="5_002e2.xhtml#g_t5_002e2" accesskey="n" rel="next">5.2</a>, Prev: <a href="Chapter-5.xhtml#Chapter-5" accesskey="p" rel="prev">Chapter 5</a>, Up: <a href="Chapter-5.xhtml#Chapter-5" accesskey="u" rel="prev">Chapter 5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Designing-Register-Machines"></a>
<h3 class="section"><span class="secnum">5.1</span><span class="sectitle">Designing Register Machines</span></h3>

<p>To design a register machine, we must design its <a id="index-data-paths"></a>
<em>data paths</em>
(registers and operations) and the <a id="index-controller"></a>
<em>controller</em> that sequences these
operations.  To illustrate the design of a simple register machine, let us
examine Euclid’s Algorithm, which is used to compute the greatest common
divisor (<abbr>GCD</abbr>) of two integers.  As we saw in <a href="1_002e2.xhtml#g_t1_002e2_002e5">1.2.5</a>,
Euclid’s Algorithm can be carried out by an iterative process, as specified by
the following procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> b </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      a
      </span><span class="opn">(</span><span class="pln">gcd b </span><span class="opn">(</span><span class="pln">remainder a b</span><span class="clo">))))</span></pre></div>

<p>A machine to carry out this algorithm must keep track of two numbers, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math> and
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, so let us assume that these numbers are stored in two registers with
those names.  The basic operations required are testing whether the contents of
register <code>b</code> is zero and computing the remainder of the contents of
register <code>a</code> divided by the contents of register <code>b</code>.  The remainder
operation is a complex process, but assume for the moment that we have a
primitive device that computes remainders.  On each cycle of the <abbr>GCD</abbr>
algorithm, the contents of register <code>a</code> must be replaced by the contents
of register <code>b</code>, and the contents of <code>b</code> must be replaced by the
remainder of the old contents of <code>a</code> divided by the old contents of
<code>b</code>.  It would be convenient if these replacements could be done
simultaneously, but in our model of register machines we will assume that only
one register can be assigned a new value at each step.  To accomplish the
replacements, our machine will use a third “temporary” register, which we
call <code>t</code>.  (First the remainder will be placed in <code>t</code>, then the
contents of <code>b</code> will be placed in <code>a</code>, and finally the remainder
stored in <code>t</code> will be placed in <code>b</code>.)
</p>
<p>We can illustrate the registers and operations required for this machine by
using the data-path diagram shown in <a href="#Figure-5_002e1">Figure 5.1</a>.  In this diagram, the
registers (<code>a</code>, <code>b</code>, and <code>t</code>) are represented by rectangles.
Each way to assign a value to a register is indicated by an arrow with an
<code>X</code> behind the head, pointing from the source of data to the register.  We
can think of the <code>X</code> as a button that, when pushed, allows the value at
the source to “flow” into the designated register.  The label next to each
button is the name we will use to refer to the button.  The names are
arbitrary, and can be chosen to have mnemonic value (for example, <code>a&lt;-b</code>
denotes pushing the button that assigns the contents of register <code>b</code> to
register <code>a</code>).  The source of data for a register can be another register
(as in the <code>a&lt;-b</code> assignment), an operation result (as in the <code>t&lt;-r</code>
assignment), or a constant (a built-in value that cannot be changed,
represented in a data-path diagram by a triangle containing the constant).
</p>
<figure class="float">
<a id="Figure-5_002e1"></a>
<object style="width: 37.90ex; height: 26.07ex;" data="fig/chap5/Fig5.1a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.1:</strong> Data paths for a <abbr>GCD</abbr> machine.</p>
</figcaption>
</figure>

<p>An operation that computes a value from constants and the contents of registers
is represented in a data-path diagram by a trapezoid containing a name for the
operation.  For example, the box marked <code>rem</code> in <a href="#Figure-5_002e1">Figure 5.1</a>
represents an operation that computes the remainder of the contents of the
registers <code>a</code> and <code>b</code> to which it is attached.  Arrows (without
buttons) point from the input registers and constants to the box, and arrows
connect the operation’s output value to registers.  A test is represented by a
circle containing a name for the test.  For example, our <abbr>GCD</abbr> machine
has an operation that tests whether the contents of register <code>b</code> is zero.
A test also has arrows from its input registers and constants, but it has no
output arrows; its value is used by the controller rather than by the data
paths.  Overall, the data-path diagram shows the registers and operations that
are required for the machine and how they must be connected.  If we view the
arrows as wires and the <code>X</code> buttons as switches, the data-path diagram is
very like the wiring diagram for a machine that could be constructed from
electrical components.
</p>
<p>In order for the data paths to actually compute <abbr>GCD</abbr>s, the buttons
must be pushed in the correct sequence.  We will describe this sequence in
terms of a controller diagram, as illustrated in <a href="#Figure-5_002e2">Figure 5.2</a>.  The
elements of the controller diagram indicate how the data-path components should
be operated.  The rectangular boxes in the controller diagram identify
data-path buttons to be pushed, and the arrows describe the sequencing from one
step to the next.  The diamond in the diagram represents a decision.  One of
the two sequencing arrows will be followed, depending on the value of the
data-path test identified in the diamond.  We can interpret the controller in
terms of a physical analogy: Think of the diagram as a maze in which a marble
is rolling.  When the marble rolls into a box, it pushes the data-path button
that is named by the box.  When the marble rolls into a decision node (such as
the test for <code>b</code> = 0), it leaves the node on the path determined by the
result of the indicated test.  Taken together, the data paths and the
controller completely describe a machine for computing <abbr>GCD</abbr>s.  We
start the controller (the rolling marble) at the place marked <code>start</code>,
after placing numbers in registers <code>a</code> and <code>b</code>.  When the controller
reaches <code>done</code>, we will find the value of the <abbr>GCD</abbr> in register
<code>a</code>.
</p>
<figure class="float">
<a id="Figure-5_002e2"></a>
<object style="width: 27.46ex; height: 30.74ex;" data="fig/chap5/Fig5.2.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.2:</strong> Controller for a <abbr>GCD</abbr> machine.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-5_002e1"></a>Exercise 5.1:</strong> Design a register machine to
compute factorials using the iterative algorithm specified by the following
procedure.  Draw data-path and controller diagrams for this machine.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter product counter</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> counter n</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> counter product</span><span class="clo">)</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter </span><span class="lit">1</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>
</blockquote>


<a id="g_t5_002e1_002e1"></a>
<a id="A-Language-for-Describing-Register-Machines"></a>
<h4 class="subsection"><span class="secnum">5.1.1</span><span class="sectitle">A Language for Describing Register Machines</span></h4>

<p>Data-path and controller diagrams are adequate for representing simple machines
such as <abbr>GCD</abbr>, but they are unwieldy for describing large machines such
as a Lisp interpreter.  To make it possible to deal with complex machines, we
will create a language that presents, in textual form, all the information
given by the data-path and controller diagrams.  We will start with a notation
that directly mirrors the diagrams.
</p>
<p>We define the data paths of a machine by describing the registers and the
operations.  To describe a register, we give it a name and specify the buttons
that control assignment to it.  We give each of these buttons a name and
specify the source of the data that enters the register under the button’s
control.  (The source is a register, a constant, or an operation.)  To describe
an operation, we give it a name and specify its inputs (registers or
constants).
</p>
<p>We define the controller of a machine as a sequence of <a id="index-instructions-1"></a>
<em>instructions</em>
together with <a id="index-labels"></a>
<em>labels</em> that identify <a id="index-entry-points"></a>
<em>entry points</em> in the
sequence. An instruction is one of the following:
</p>
<ul>
<li> The name of a data-path button to push to assign a value to a register.  (This
corresponds to a box in the controller diagram.)

</li><li> A <code>test</code> instruction, that performs a specified test.

</li><li> A conditional branch (<code>branch</code> instruction) to a location indicated by a
controller label, based on the result of the previous test.  (The test and
branch together correspond to a diamond in the controller diagram.)  If the
test is false, the controller should continue with the next instruction in the
sequence.  Otherwise, the controller should continue with the instruction after
the label.

</li><li> An unconditional branch (<code>goto</code> instruction) naming a controller label at
which to continue execution.

</li></ul>

<p>The machine starts at the beginning of the controller instruction sequence and
stops when execution reaches the end of the sequence.  Except when a branch
changes the flow of control, instructions are executed in the order in which
they are listed.
</p>
<p><a href="#Figure-5_002e3">Figure 5.3</a> shows the <abbr>GCD</abbr> machine described in this way.  This
example only hints at the generality of these descriptions, since the
<abbr>GCD</abbr> machine is a very simple case: Each register has only one button,
and each button and test is used only once in the controller.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e3"></a>Figure 5.3:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> A specification of the <abbr>GCD</abbr>
machine.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">data-paths
 </span><span class="opn">(</span><span class="pln">registers
  </span><span class="opn">((</span><span class="pln">name a</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">buttons </span><span class="opn">((</span><span class="pln">name a</span><span class="pun">&lt;-</span><span class="pln">b</span><span class="clo">)</span><span class="pln"> 
             </span><span class="opn">(</span><span class="pln">source </span><span class="opn">(</span><span class="pln">register b</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">name b</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">buttons </span><span class="opn">((</span><span class="pln">name b</span><span class="pun">&lt;-</span><span class="pln">t</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">source </span><span class="opn">(</span><span class="pln">register t</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">name t</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">buttons </span><span class="opn">((</span><span class="pln">name t</span><span class="pun">&lt;-</span><span class="pln">r</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">source </span><span class="opn">(</span><span class="pln">operation rem</span><span class="clo">))))))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">operations
  </span><span class="opn">((</span><span class="pln">name rem</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">inputs </span><span class="opn">(</span><span class="pln">register a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">register b</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">((</span><span class="pln">name </span><span class="pun">=</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">inputs </span><span class="opn">(</span><span class="pln">register b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">constant </span><span class="lit">0</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">controller
 test-b                </span><span class="roman"><span class="com">; label</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">test </span><span class="pun">=</span><span class="clo">)</span><span class="pln">            </span><span class="roman"><span class="com">; test</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">branch 
    </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">  </span><span class="roman"><span class="com">; conditional branch</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">t</span><span class="pun">&lt;-</span><span class="pln">r</span><span class="clo">)</span><span class="pln">              </span><span class="roman"><span class="com">; button push</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">a</span><span class="pun">&lt;-</span><span class="pln">b</span><span class="clo">)</span><span class="pln">              </span><span class="roman"><span class="com">; button push</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">b</span><span class="pun">&lt;-</span><span class="pln">t</span><span class="clo">)</span><span class="pln">              </span><span class="roman"><span class="com">; button push</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto 
    </span><span class="opn">(</span><span class="pln">label test-b</span><span class="clo">))</span><span class="pln">    </span><span class="roman"><span class="com">; unconditional branch</span></span><span class="pln">
 gcd-done</span><span class="clo">)</span><span class="pln">             </span><span class="roman"><span class="com">; label</span></span>
</pre></div>

</blockquote>

<p>Unfortunately, it is difficult to read such a description.  In order to
understand the controller instructions we must constantly refer back to the
definitions of the button names and the operation names, and to understand what
the buttons do we may have to refer to the definitions of the operation names.
We will thus transform our notation to combine the information from the
data-path and controller descriptions so that we see it all together.
</p>
<p>To obtain this form of description, we will replace the arbitrary button and
operation names by the definitions of their behavior.  That is, instead of
saying (in the controller) “Push button <code>t&lt;-r</code>” and separately saying
(in the data paths) “Button <code>t&lt;-r</code> assigns the value of the <code>rem</code>
operation to register <code>t</code>” and “The <code>rem</code> operation’s inputs are
the contents of registers <code>a</code> and <code>b</code>,” we will say (in the
controller) “Push the button that assigns to register <code>t</code> the value of
the <code>rem</code> operation on the contents of registers <code>a</code> and <code>b</code>.”
Similarly, instead of saying (in the controller) “Perform the <code>=</code> test”
and separately saying (in the data paths) “The <code>=</code> test operates on the
contents of register <code>b</code> and the constant 0,” we will say “Perform the
<code>=</code> test on the contents of register <code>b</code> and the constant 0.”  We
will omit the data-path description, leaving only the controller sequence.
Thus, the <abbr>GCD</abbr> machine is described as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">controller
 test-b
   </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label test-b</span><span class="clo">))</span><span class="pln">
 gcd-done</span><span class="clo">)</span></pre></div>

<p>This form of description is easier to read than the kind illustrated in
<a href="#Figure-5_002e3">Figure 5.3</a>, but it also has disadvantages:
</p>
<ul>
<li> It is more verbose for large machines, because complete descriptions of the
data-path elements are repeated whenever the elements are mentioned in the
controller instruction sequence.  (This is not a problem in the <abbr>GCD</abbr>
example, because each operation and button is used only once.)  Moreover,
repeating the data-path descriptions obscures the actual data-path structure of
the machine; it is not obvious for a large machine how many registers,
operations, and buttons there are and how they are interconnected.

</li><li> Because the controller instructions in a machine definition look like Lisp
expressions, it is easy to forget that they are not arbitrary Lisp expressions.
They can notate only legal machine operations.  For example, operations can
operate directly only on constants and the contents of registers, not on the
results of other operations.

</li></ul>

<p>In spite of these disadvantages, we will use this register-machine language
throughout this chapter, because we will be more concerned with understanding
controllers than with understanding the elements and connections in data paths.
We should keep in mind, however, that data-path design is crucial in designing
real machines.
</p>
<blockquote>
<p><strong><a id="Exercise-5_002e2"></a>Exercise 5.2:</strong> Use the register-machine language
to describe the iterative factorial machine of <a href="#Exercise-5_002e1">Exercise 5.1</a>.
</p></blockquote>

<a id="Actions"></a>
<h5 class="subsubheading">Actions</h5>

<p>Let us modify the <abbr>GCD</abbr> machine so that we can type in the numbers
whose <abbr>GCD</abbr> we want and get the answer printed at our terminal.  We
will not discuss how to make a machine that can read and print, but will assume
(as we do when we use <code>read</code> and <code>display</code> in Scheme) that they are
available as primitive operations.<a class="footnote_link" id="DOCF286" href="#FOOT286"><sup>286</sup></a>
</p>
<p><code>Read</code> is like the operations we have been using in that it produces a
value that can be stored in a register.  But <code>read</code> does not take inputs
from any registers; its value depends on something that happens outside the
parts of the machine we are designing.  We will allow our machine’s operations
to have such behavior, and thus will draw and notate the use of <code>read</code>
just as we do any other operation that computes a value.
</p>
<p><code>Print</code>, on the other hand, differs from the operations we have been using
in a fundamental way: It does not produce an output value to be stored in a
register.  Though it has an effect, this effect is not on a part of the machine
we are designing.  We will refer to this kind of operation as an
<a id="index-action"></a>
<em>action</em>.  We will represent an action in a data-path diagram just as
we represent an operation that computes a value—as a trapezoid that contains
the name of the action.  Arrows point to the action box from any inputs
(registers or constants).  We also associate a button with the action.  Pushing
the button makes the action happen.  To make a controller push an action button
we use a new kind of instruction called <code>perform</code>.  Thus, the action of
printing the contents of register <code>a</code> is represented in a controller
sequence by the instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op print</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">))</span></pre></div>

<p><a href="#Figure-5_002e4">Figure 5.4</a> shows the data paths and controller for the new <abbr>GCD</abbr>
machine.  Instead of having the machine stop after printing the answer, we have
made it start over, so that it repeatedly reads a pair of numbers, computes
their <abbr>GCD</abbr>, and prints the result.  This structure is like the driver
loops we used in the interpreters of <a href="Chapter-4.xhtml#Chapter-4">Chapter 4</a>.
</p>
<figure class="float">
<a id="Figure-5_002e4"></a>
<object style="width: 59.92ex; height: 69.76ex;" data="fig/chap5/Fig5.4c.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.4:</strong> A <abbr>GCD</abbr> machine that reads inputs and prints results.</p>
</figcaption>
</figure>

<a id="g_t5_002e1_002e2"></a>
<a id="Abstraction-in-Machine-Design"></a>
<h4 class="subsection"><span class="secnum">5.1.2</span><span class="sectitle">Abstraction in Machine Design</span></h4>

<p>We will often define a machine to include “primitive” operations that are
actually very complex.  For example, in <a href="5_002e4.xhtml#g_t5_002e4">5.4</a> and <a href="5_002e5.xhtml#g_t5_002e5">5.5</a> we
will treat Scheme’s environment manipulations as primitive.  Such abstraction
is valuable because it allows us to ignore the details of parts of a machine so
that we can concentrate on other aspects of the design.  The fact that we have
swept a lot of complexity under the rug, however, does not mean that a machine
design is unrealistic.  We can always replace the complex “primitives” by
simpler primitive operations.
</p>
<p>Consider the <abbr>GCD</abbr> machine. The machine has an instruction that
computes the remainder of the contents of registers <code>a</code> and <code>b</code> and
assigns the result to register <code>t</code>.  If we want to construct the
<abbr>GCD</abbr> machine without using a primitive remainder operation, we must
specify how to compute remainders in terms of simpler operations, such as
subtraction.  Indeed, we can write a Scheme procedure that finds remainders in
this way:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remainder n d</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> n d</span><span class="clo">)</span><span class="pln"> n </span><span class="opn">(</span><span class="pln">remainder </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n d</span><span class="clo">)</span><span class="pln"> d</span><span class="clo">)))</span></pre></div>

<p>We can thus replace the remainder operation in the <abbr>GCD</abbr> machine’s data
paths with a subtraction operation and a comparison test.  <a href="#Figure-5_002e5">Figure 5.5</a>
shows the data paths and controller for the elaborated machine.  The
instruction
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span></pre></div>

<p>in the <abbr>GCD</abbr> controller definition is replaced by a sequence of
instructions that contains a loop, as shown in <a href="#Figure-5_002e6">Figure 5.6</a>.
</p>
<figure class="float">
<a id="Figure-5_002e5"></a>
<object style="width: 44.03ex; height: 70.71ex;" data="fig/chap5/Fig5.5b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.5:</strong> Data paths and controller for the elaborated <abbr>GCD</abbr> machine.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Figure-5_002e6"></a>Figure 5.6:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Controller instruction sequence for the
<abbr>GCD</abbr> machine in <a href="#Figure-5_002e5">Figure 5.5</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">controller
 test-b
   </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">))</span><span class="pln">
 rem-loop
   </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">&lt;</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label rem-done</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op </span><span class="pun">-</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label rem-loop</span><span class="clo">))</span><span class="pln">
 rem-done
   </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label test-b</span><span class="clo">))</span><span class="pln">
 gcd-done</span><span class="clo">)</span></pre></div>

</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e3"></a>Exercise 5.3:</strong> Design a machine to compute square
roots using Newton’s method, as described in <a href="1_002e1.xhtml#Sec_002e1_002e1_002e7">1.1.7</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">abs </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square guess</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">improve guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">average guess </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x guess</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-iter guess</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">good-enough? guess</span><span class="clo">)</span><span class="pln">
        guess
        </span><span class="opn">(</span><span class="pln">sqrt-iter </span><span class="opn">(</span><span class="pln">improve guess</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">sqrt-iter </span><span class="lit">1.0</span><span class="clo">))</span></pre></div>

<p>Begin by assuming that <code>good-enough?</code> and <code>improve</code> operations are
available as primitives.  Then show how to expand these in terms of arithmetic
operations.  Describe each version of the <code>sqrt</code> machine design by drawing
a data-path diagram and writing a controller definition in the register-machine
language.
</p></blockquote>

<a id="g_t5_002e1_002e3"></a>
<a id="Subroutines"></a>
<h4 class="subsection"><span class="secnum">5.1.3</span><span class="sectitle">Subroutines</span></h4>

<p>When designing a machine to perform a computation, we would often prefer to
arrange for components to be shared by different parts of the computation
rather than duplicate the components.  Consider a machine that includes two
<abbr>GCD</abbr> computations—one that finds the <abbr>GCD</abbr> of the contents
of registers <code>a</code> and <code>b</code> and one that finds the <abbr>GCD</abbr> of the
contents of registers <code>c</code> and <code>d</code>.  We might start by assuming we
have a primitive <code>gcd</code> operation, then expand the two instances of
<code>gcd</code> in terms of more primitive operations.  <a href="#Figure-5_002e7">Figure 5.7</a> shows just
the <abbr>GCD</abbr> portions of the resulting machine’s data paths, without
showing how they connect to the rest of the machine.  The figure also shows the
corresponding portions of the machine’s controller sequence.
</p>
<figure class="float">
<a id="Figure-5_002e7"></a>
<object style="width: 56.64ex; height: 63.20ex;" data="fig/chap5/Fig5.7b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.7:</strong> Portions of the data paths and controller sequence<!-- /@w --> for a machine with two <abbr>GCD</abbr> computations.</p>
</figcaption>
</figure>

<p>This machine has two remainder operation boxes and two boxes for testing
equality.  If the duplicated components are complicated, as is the remainder
box, this will not be an economical way to build the machine.  We can avoid
duplicating the data-path components by using the same components for both
<abbr>GCD</abbr> computations, provided that doing so will not affect the rest of
the larger machine’s computation.  If the values in registers <code>a</code> and
<code>b</code> are not needed by the time the controller gets to <code>gcd-2</code> (or if
these values can be moved to other registers for safekeeping), we can change
the machine so that it uses registers <code>a</code> and <code>b</code>, rather than
registers <code>c</code> and <code>d</code>, in computing the second <abbr>GCD</abbr> as well
as the first.  If we do this, we obtain the controller sequence shown in
<a href="#Figure-5_002e8">Figure 5.8</a>.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e8"></a>Figure 5.8:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Portions of the controller sequence for
a machine that uses the same data-path components for two different
<abbr>GCD</abbr> computations.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">gcd-1
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label after-gcd-1</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd-1</span><span class="clo">))</span><span class="pln">
after-gcd-1
  </span><span class="roman"><span class="pun">…</span></span><span class="pln">
gcd-2
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label after-gcd-2</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd-2</span><span class="clo">))</span><span class="pln">
after-gcd-2</span></pre></div>

</blockquote>

<p>We have removed the duplicate data-path components (so that the data paths are
again as in <a href="#Figure-5_002e1">Figure 5.1</a>), but the controller now has two <abbr>GCD</abbr>
sequences that differ only in their entry-point labels.  It would be better to
replace these two sequences by branches to a single sequence—a <code>gcd</code>
<a id="index-subroutine"></a>
<em>subroutine</em>—at the end of which we branch back to the correct place
in the main instruction sequence.  We can accomplish this as follows: Before
branching to <code>gcd</code>, we place a distinguishing value (such as 0 or 1) into
a special register, <code>continue</code>.  At the end of the <code>gcd</code> subroutine
we return either to <code>after-gcd-1</code> or to <code>after-gcd-2</code>, depending on
the value of the <code>continue</code> register.  <a href="#Figure-5_002e9">Figure 5.9</a> shows the relevant
portion of the resulting controller sequence, which includes only a single copy
of the <code>gcd</code> instructions.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e9"></a>Figure 5.9:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Using a <code>continue</code> register to
avoid the duplicate controller sequence in <a href="#Figure-5_002e8">Figure 5.8</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">gcd
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
gcd-done
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label after-gcd-1</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label after-gcd-2</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="pun">…</span></span><span class="pln">
</span><span class="roman"><span class="com">;; Before branching to </span><code><span class="com">gcd</span></code><span class="com"> from</span></span><span class="pln">
</span><span class="roman"><span class="com">;; the first place where it is needed,</span></span><span class="pln">
</span><span class="roman"><span class="com">;; we place 0 in the </span><code><span class="com">continue</span></code><span class="com"> register</span></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
after-gcd-1
  </span><span class="roman"><span class="pun">…</span></span><span class="pln">
</span><span class="roman"><span class="com">;; Before the second use of </span><code><span class="com">gcd</span></code><span class="com">,</span></span><span class="com"> </span><span class="pln">
</span><span class="roman"><span class="com">;; we place 1 in the </span><code><span class="com">continue</span></code><span class="com"> register</span></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
after-gcd-2</span></pre></div>

</blockquote>

<p>This is a reasonable approach for handling small problems, but it would be
awkward if there were many instances of <abbr>GCD</abbr> computations in the
controller sequence.  To decide where to continue executing after the
<code>gcd</code> subroutine, we would need tests in the data paths and branch
instructions in the controller for all the places that use <code>gcd</code>.  A more
powerful method for implementing subroutines is to have the <code>continue</code>
register hold the label of the entry point in the controller sequence at which
execution should continue when the subroutine is finished.  Implementing this
strategy requires a new kind of connection between the data paths and the
controller of a register machine: There must be a way to assign to a register a
label in the controller sequence in such a way that this value can be fetched
from the register and used to continue execution at the designated entry point.
</p>
<p>To reflect this ability, we will extend the <code>assign</code> instruction of the
register-machine language to allow a register to be assigned as value a label
from the controller sequence (as a special kind of constant).  We will also
extend the <code>goto</code> instruction to allow execution to continue at the entry
point described by the contents of a register rather than only at an entry
point described by a constant label.  Using these new constructs we can
terminate the <code>gcd</code> subroutine with a branch to the location stored in the
<code>continue</code> register.  This leads to the controller sequence shown in
<a href="#Figure-5_002e10">Figure 5.10</a>.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e10"></a>Figure 5.10:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Assigning labels to the
<code>continue</code> register simplifies and generalizes the strategy shown in
<a href="#Figure-5_002e9">Figure 5.9</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="pln">gcd
 </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">=</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label gcd-done</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign t </span><span class="opn">(</span><span class="pln">op rem</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg a</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign a </span><span class="opn">(</span><span class="pln">reg b</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign b </span><span class="opn">(</span><span class="pln">reg t</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
gcd-done
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
  </span><span class="roman"><span class="pun">…</span></span><span class="pln">
</span><span class="roman"><span class="com">;; Before calling </span><code><span class="com">gcd</span></code><span class="com">,</span></span><span class="com"> </span><span class="pln">
</span><span class="roman"><span class="com">;; we assign to </span><code><span class="com">continue</span></code><span class="com"> the label</span></span><span class="pln">
</span><span class="roman"><span class="com">;; to which </span><code><span class="com">gcd</span></code><span class="com"> should return.</span></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-gcd-1</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
after-gcd-1
  </span><span class="roman"><span class="pun">…</span></span><span class="pln">
</span><span class="roman"><span class="com">;; Here is the second call to </span><code><span class="com">gcd</span></code><span class="com">,</span></span><span class="pln">
</span><span class="roman"><span class="com">;; with a different continuation.</span></span><span class="pln">
 </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label after-gcd-2</span><span class="clo">))</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label gcd</span><span class="clo">))</span><span class="pln">
after-gcd-2</span></pre></div>

</blockquote>

<p>A machine with more than one subroutine could use multiple continuation
registers (e.g., <code>gcd-continue</code>, <code>factorial-continue</code>) or we could
have all subroutines share a single <code>continue</code> register.  Sharing is more
economical, but we must be careful if we have a subroutine (<code>sub1</code>) that
calls another subroutine (<code>sub2</code>).  Unless <code>sub1</code> saves the contents
of <code>continue</code> in some other register before setting up <code>continue</code> for
the call to <code>sub2</code>, <code>sub1</code> will not know where to go when it is
finished.  The mechanism developed in the next section to handle recursion also
provides a better solution to this problem of nested subroutine calls.
</p>
<a id="g_t5_002e1_002e4"></a>
<a id="Using-a-Stack-to-Implement-Recursion"></a>
<h4 class="subsection"><span class="secnum">5.1.4</span><span class="sectitle">Using a Stack to Implement Recursion</span></h4>

<p>With the ideas illustrated so far, we can implement any iterative process by
specifying a register machine that has a register corresponding to each state
variable of the process.  The machine repeatedly executes a controller loop,
changing the contents of the registers, until some termination condition is
satisfied.  At each point in the controller sequence, the state of the machine
(representing the state of the iterative process) is completely determined by
the contents of the registers (the values of the state variables).
</p>
<p>Implementing recursive processes, however, requires an additional mechanism.
Consider the following recursive method for computing factorials, which we
first examined in <a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> 
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="opn">(</span><span class="pln">factorial </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)))</span></pre></div>

<p>As we see from the procedure, computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math> requires computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math>.
Our <abbr>GCD</abbr> machine, modeled on the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> b </span><span class="lit">0</span><span class="clo">)</span><span class="pln"> 
      a
      </span><span class="opn">(</span><span class="pln">gcd b </span><span class="opn">(</span><span class="pln">remainder a b</span><span class="clo">))))</span></pre></div>

<p>similarly had to compute another <abbr>GCD</abbr>.  But there is an important
difference between the <code>gcd</code> procedure, which reduces the original
computation to a new <abbr>GCD</abbr> computation, and <code>factorial</code>, which
requires computing another factorial as a subproblem.  In <abbr>GCD</abbr>, the
answer to the new <abbr>GCD</abbr> computation is the answer to the original
problem.  To compute the next <abbr>GCD</abbr>, we simply place the new arguments
in the input registers of the <abbr>GCD</abbr> machine and reuse the machine’s
data paths by executing the same controller sequence.  When the machine is
finished solving the final <abbr>GCD</abbr> problem, it has completed the entire
computation.
</p>
<p>In the case of factorial (or any recursive process) the answer to the new
factorial subproblem is not the answer to the original problem.  The value
obtained for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math> must be multiplied by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> to get the final answer.
If we try to imitate the <abbr>GCD</abbr> design, and solve the factorial
subproblem by decrementing the <code>n</code> register and rerunning the factorial
machine, we will no longer have available the old value of <code>n</code> by which to
multiply the result.  We thus need a second factorial machine to work on the
subproblem.  This second factorial computation itself has a factorial
subproblem, which requires a third factorial machine, and so on.  Since each
factorial machine contains another factorial machine within it, the total
machine contains an infinite nest of similar machines and hence cannot be
constructed from a fixed, finite number of parts.
</p>
<p>Nevertheless, we can implement the factorial process as a register machine if
we can arrange to use the same components for each nested instance of the
machine.  Specifically, the machine that computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>  should use the same
components to work on the subproblem of computing <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math>, on the
subproblem for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math>, and so on.  This is plausible because, although
the factorial process dictates that an unbounded number of copies of the same
machine are needed to perform a computation, only one of these copies needs to
be active at any given time.  When the machine encounters a recursive
subproblem, it can suspend work on the main problem, reuse the same physical
parts to work on the subproblem, then continue the suspended computation.
</p>
<p>In the subproblem, the contents of the registers will be different than they
were in the main problem. (In this case the <code>n</code> register is decremented.)
In order to be able to continue the suspended computation, the machine must
save the contents of any registers that will be needed after the subproblem is
solved so that these can be restored to continue the suspended computation.  In
the case of factorial, we will save the old value of <code>n</code>, to be restored
when we are finished computing the factorial of the decremented <code>n</code>
register.<a class="footnote_link" id="DOCF287" href="#FOOT287"><sup>287</sup></a>
</p>
<p>Since there is no <em>a priori</em> limit on the depth of nested recursive calls,
we may need to save an arbitrary number of register values.  These values must
be restored in the reverse of the order in which they were saved, since in a
nest of recursions the last subproblem to be entered is the first to be
finished.  This dictates the use of a <a id="index-stack-1"></a>
<em>stack</em>, or “last in, first
out” data structure, to save register values.  We can extend the
register-machine language to include a stack by adding two kinds of
instructions: Values are placed on the stack using a <code>save</code> instruction
and restored from the stack using a <code>restore</code> instruction.  After a
sequence of values has been <code>save</code>d on the stack, a sequence of
<code>restore</code>s will retrieve these values in reverse order.<a class="footnote_link" id="DOCF288" href="#FOOT288"><sup>288</sup></a>
</p>
<p>With the aid of the stack, we can reuse a single copy of the factorial
machine’s data paths for each factorial subproblem.  There is a similar design
issue in reusing the controller sequence that operates the data paths.  To
reexecute the factorial computation, the controller cannot simply loop back to
the beginning, as with an iterative process, because after solving the 
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math> subproblem the machine must still multiply the result by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.  The
controller must suspend its computation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>, solve the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
    <mo>!</mo>
  </mrow>
</math>
subproblem, then continue its computation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>!</mo>
  </mrow>
</math>.  This view of the
factorial computation suggests the use of the subroutine mechanism described in
<a href="#g_t5_002e1_002e3">5.1.3</a>, which has the controller use a <code>continue</code> register to
transfer to the part of the sequence that solves a subproblem and then continue
where it left off on the main problem.  We can thus make a factorial subroutine
that returns to the entry point stored in the <code>continue</code> register.  Around
each subroutine call, we save and restore <code>continue</code> just as we do the
<code>n</code> register, since each “level” of the factorial computation will use
the same <code>continue</code> register.  That is, the factorial subroutine must put
a new value in <code>continue</code> when it calls itself for a subproblem, but it
will need the old value in order to return to the place that called it to solve
a subproblem.
</p>
<p><a href="#Figure-5_002e11">Figure 5.11</a> shows the data paths and controller for a machine that
implements the recursive <code>factorial</code> procedure.  The machine has a stack
and three registers, called <code>n</code>, <code>val</code>, and <code>continue</code>.  To
simplify the data-path diagram, we have not named the register-assignment
buttons, only the stack-operation buttons (<code>sc</code> and <code>sn</code> to save
registers, <code>rc</code> and <code>rn</code> to restore registers).  To operate the
machine, we put in register <code>n</code> the number whose factorial we wish to
compute and start the machine.  When the machine reaches <code>fact-done</code>, the
computation is finished and the answer will be found in the <code>val</code>
register.  In the controller sequence, <code>n</code> and <code>continue</code> are saved
before each recursive call and restored upon return from the call.  Returning
from a call is accomplished by branching to the location stored in
<code>continue</code>.  <code>Continue</code> is initialized when the machine starts so
that the last return will go to <code>fact-done</code>.  The <code>val</code> register,
which holds the result of the factorial computation, is not saved before the
recursive call, because the old contents of <code>val</code> is not useful after the
subroutine returns.  Only the new value, which is the value produced by the
subcomputation, is needed.
</p>
<figure class="float">
<a id="Figure-5_002e11"></a>
<object style="width: 66.14ex; height: 73.13ex;" data="fig/chap5/Fig5.11b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 5.11:</strong> A recursive factorial machine.</p>
</figcaption>
</figure>

<p>Although in principle the factorial computation requires an infinite machine,
the machine in <a href="#Figure-5_002e11">Figure 5.11</a> is actually finite except for the stack, which
is potentially unbounded.  Any particular physical implementation of a stack,
however, will be of finite size, and this will limit the depth of recursive
calls that can be handled by the machine.  This implementation of factorial
illustrates the general strategy for realizing recursive algorithms as ordinary
register machines augmented by stacks.  When a recursive subproblem is
encountered, we save on the stack the registers whose current values will be
required after the subproblem is solved, solve the recursive subproblem, then
restore the saved registers and continue execution on the main problem.  The
<code>continue</code> register must always be saved.  Whether there are other
registers that need to be saved depends on the particular machine, since not
all recursive computations need the original values of registers that are
modified during solution of the subproblem (see <a href="#Exercise-5_002e4">Exercise 5.4</a>).
</p>
<a id="A-double-recursion"></a>
<h5 class="subsubheading">A double recursion</h5>

<p>Let us examine a more complex recursive process, the tree-recursive computation
of the Fibonacci numbers, which we introduced in <a href="1_002e2.xhtml#g_t1_002e2_002e2">1.2.2</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&lt;</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)</span><span class="pln"> 
      n 
      </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fib </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)))))</span></pre></div>

<p>Just as with factorial, we can implement the recursive Fibonacci computation as
a register machine with registers <code>n</code>, <code>val</code>, and <code>continue</code>.
The machine is more complex than the one for factorial, because there are two
places in the controller sequence where we need to perform recursive
calls—once to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and once to compute <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mtext>Fib</mtext>
    <mo stretchy="false">(</mo>
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  To
set up for each of these calls, we save the registers whose values will be
needed later, set the <code>n</code> register to the number whose Fib we need to
compute recursively (<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>−<!-- − --></mo>
    <mn>2</mn>
  </mrow>
</math>), and assign to <code>continue</code> the
entry point in the main sequence to which to return (<code>afterfib-n-1</code> or
<code>afterfib-n-2</code>, respectively).  We then go to <code>fib-loop</code>.  When we
return from the recursive call, the answer is in <code>val</code>.  <a href="#Figure-5_002e12">Figure 5.12</a>
shows the controller sequence for this machine.
</p>
<blockquote>
<p><strong><a id="Figure-5_002e12"></a>Figure 5.12:</strong> <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mo stretchy="false">↓<!-- ↓ --></mo>
</math> Controller for a machine to compute
Fibonacci numbers.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">controller
   </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label fib-done</span><span class="clo">))</span><span class="pln">
 fib-loop
   </span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op </span><span class="pun">&lt;</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label immediate-answer</span><span class="clo">))</span><span class="pln">
   </span><span class="roman"><span class="com">;; set up to compute Fib(</span><em><span class="com">n</span></em><span class="com"> − 1)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label afterfib-n-1</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">save n</span><span class="clo">)</span><span class="pln">           </span><span class="roman"><span class="com">; save old value of </span><code><span class="com">n</span></code></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign n 
           </span><span class="opn">(</span><span class="pln">op </span><span class="pun">-</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg n</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">const </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> </span><span class="roman"><span class="com">; clobber </span><code><span class="com">n</span></code><span class="com"> to </span><code><span class="com">n-1</span></code></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto 
    </span><span class="opn">(</span><span class="pln">label fib-loop</span><span class="clo">))</span><span class="pln"> </span><span class="roman"><span class="com">; perform recursive call</span></span><span class="pln">
 afterfib-n-1 </span><span class="roman"><span class="com">; upon return, </span><code><span class="com">val</span></code><span class="com"> contains Fib(</span><em><span class="com">n</span></em><span class="com"> − 1)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">restore n</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
   </span><span class="roman"><span class="com">;; set up to compute Fib(</span><em><span class="com">n</span></em><span class="com"> − 2)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign n </span><span class="opn">(</span><span class="pln">op </span><span class="pun">-</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">reg n</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">const </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">save continue</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign continue </span><span class="opn">(</span><span class="pln">label afterfib-n-2</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">save val</span><span class="clo">)</span><span class="pln">         </span><span class="roman"><span class="com">; save Fib(</span><em><span class="com">n</span></em><span class="com"> − 1)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label fib-loop</span><span class="clo">))</span><span class="pln">
 afterfib-n-2 </span><span class="roman"><span class="com">; upon return, </span><code><span class="com">val</span></code><span class="com"> contains Fib(</span><em><span class="com">n</span></em><span class="com"> − 2)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign n 
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">))</span><span class="pln"> </span><span class="roman"><span class="com">; </span><code><span class="com">n</span></code><span class="com"> now contains Fib(</span><em><span class="com">n</span></em><span class="com"> − 2)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">restore val</span><span class="clo">)</span><span class="pln">      </span><span class="roman"><span class="com">; </span><code><span class="com">val</span></code><span class="com"> now contains Fib(</span><em><span class="com">n</span></em><span class="com"> − 1)</span></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">restore continue</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">assign val        </span><span class="roman"><span class="com">; Fib(</span><em><span class="com">n</span></em><span class="com"> − 1) + Fib(</span><em><span class="com">n</span></em><span class="com"> − 2)</span></span><span class="pln">
           </span><span class="opn">(</span><span class="pln">op </span><span class="pun">+</span><span class="clo">)</span><span class="pln"> 
           </span><span class="opn">(</span><span class="pln">reg val</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">reg n</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto              </span><span class="roman"><span class="com">; return to caller,</span></span><span class="pln">
    </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; answer is in </span><code><span class="com">val</span></code></span><span class="pln">
 immediate-answer
   </span><span class="opn">(</span><span class="pln">assign val 
           </span><span class="opn">(</span><span class="pln">reg n</span><span class="clo">))</span><span class="pln">   </span><span class="roman"><span class="com">; base case: Fib(</span><em><span class="com">n</span></em><span class="com">) = </span><em><span class="com">n</span></em></span><span class="pln">
   </span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg continue</span><span class="clo">))</span><span class="pln">
 fib-done</span><span class="clo">)</span></pre></div>

</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e4"></a>Exercise 5.4:</strong> Specify register machines that
implement each of the following procedures.  For each machine, write a
controller instruction sequence and draw a diagram showing the data paths.
</p>
<ol>
<li> Recursive exponentiation:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt b n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">1</span><span class="pln">
      </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b </span><span class="opn">(</span><span class="pln">expt b </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">)))))</span></pre></div>

</li><li> Iterative exponentiation:

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt b n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expt-iter counter product</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> counter </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
        product
        </span><span class="opn">(</span><span class="pln">expt-iter </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> counter </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                   </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> b product</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">expt-iter n </span><span class="lit">1</span><span class="clo">))</span></pre></div>

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e5"></a>Exercise 5.5:</strong> Hand-simulate the factorial and
Fibonacci machines, using some nontrivial input (requiring execution of at
least one recursive call).  Show the contents of the stack at each significant
point in the execution.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-5_002e6"></a>Exercise 5.6:</strong> Ben Bitdiddle observes that the
Fibonacci machine’s controller sequence has an extra <code>save</code> and an extra
<code>restore</code>, which can be removed to make a faster machine.  Where are these
instructions?
</p></blockquote>

<a id="g_t5_002e1_002e5"></a>
<a id="Instruction-Summary"></a>
<h4 class="subsection"><span class="secnum">5.1.5</span><span class="sectitle">Instruction Summary</span></h4>

<p>A controller instruction in our register-machine language has one of the
following forms, where each <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">⟨</mo>
    <mspace width="0.06em"/>
    <mi>i</mi>
    <mi>n</mi>
    <mi>p</mi>
    <mi>u</mi>
    <msub>
      <mi>t</mi>
      <mi>i</mi>
    </msub>
    <mo stretchy="false">⟩</mo>
  </mrow>
</math> is either 
<code>(reg ⟨<var>register-name</var>⟩)</code> or <code>(const ⟨<var>constant-value</var>⟩)</code>.  
These instructions were introduced in <a href="#g_t5_002e1_002e1">5.1.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩ 
        </span><span class="opn">(</span><span class="pln">const ⟨</span><var><span class="pln">constant-value</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩ 
        </span><span class="opn">(</span><span class="pln">op ⟨</span><var><span class="pln">operation-name</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> 
        ⟨</span><var><span class="pln">input</span><span class="pun">₁</span></var><span class="pln">⟩ </span><span class="roman"><span class="pun">…</span></span><span class="pln"> ⟨</span><var><span class="pln">input</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">perform </span><span class="opn">(</span><span class="pln">op ⟨</span><var><span class="pln">operation-name</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> 
         ⟨</span><var><span class="pln">input</span><span class="pun">₁</span></var><span class="pln">⟩ 
         </span><span class="roman"><span class="pun">…</span></span><span class="pln"> 
         ⟨</span><var><span class="pln">input</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">test </span><span class="opn">(</span><span class="pln">op ⟨</span><var><span class="pln">operation-name</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln"> 
      ⟨</span><var><span class="pln">input</span><span class="pun">₁</span></var><span class="pln">⟩ 
      </span><span class="roman"><span class="pun">…</span></span><span class="pln"> 
      ⟨</span><var><span class="pln">input</span><span class="pun">ₙ</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">branch </span><span class="opn">(</span><span class="pln">label ⟨</span><var><span class="pln">label-name</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">label ⟨</span><var><span class="pln">label-name</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>The use of registers to hold labels was introduced in <a href="#g_t5_002e1_002e3">5.1.3</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">assign ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">label ⟨</span><var><span class="pln">label-name</span></var><span class="pln">⟩</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="pln">goto </span><span class="opn">(</span><span class="pln">reg ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>Instructions to use the stack were introduced in <a href="#g_t5_002e1_002e4">5.1.4</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">save ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">restore ⟨</span><var><span class="pln">register-name</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>The only kind of <code>⟨</code><var>constant-value</var><code>⟩</code> we have seen so far is a number,
but later we will use strings, symbols, and lists.
For example,<br />
<code>(const "abc")</code> is the string <code>"abc"</code>,<br />
<code>(const abc)</code> is the symbol <code>abc</code>,<br />
<code>(const (a b c))</code> is the list <code>(a b c)</code>,<br />
and <code>(const ())</code> is the empty list.
</p>
<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT286"><p><a class="footnote_backlink" href="#DOCF286"><sup>286</sup></a>
This assumption glosses over a
great deal of complexity.  Usually a large portion of the implementation of a
Lisp system is dedicated to making reading and printing work.</p>
</div>
<div id="FOOT287"><p><a class="footnote_backlink" href="#DOCF287"><sup>287</sup></a>
One might argue that we don’t need to save the old <code>n</code>;
after we decrement it and solve the subproblem, we could simply increment it to
recover the old value.  Although this strategy works for factorial, it cannot
work in general, since the old value of a register cannot always be computed
from the new one.</p>
</div>
<div id="FOOT288"><p><a class="footnote_backlink" href="#DOCF288"><sup>288</sup></a>
In
<a href="5_002e3.xhtml#g_t5_002e3">5.3</a> we will see how to implement a stack in terms of more
primitive operations.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="5_002e2.xhtml#g_t5_002e2" accesskey="n" rel="next">5.2</a>, Prev: <a href="Chapter-5.xhtml#Chapter-5" accesskey="p" rel="prev">Chapter 5</a>, Up: <a href="#g_t5_002e1" accesskey="u" rel="prev">5.1</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>